from math import inf
from typing import Optional

# https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/
# 1373. 二叉搜索子树的最大键值和


class TreeNode:

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def maxSumBST(self, root: Optional[TreeNode]) -> int:

        def f(root: Optional[TreeNode]):
            if root is None:
                return [1, inf, -inf, 0, 0]
            v = root.val
            l = f(root.left)
            r = f(root.right)
            if l[0] and r[0] and v < r[1] and v > l[2]:
                s = l[3] + r[3] + v
                return [1, min(v, l[1]), max(v, r[2]), s, max(s, l[4], r[4])]
            return [0, -inf, inf, 0, max(l[4], r[4])]

        return f(root)[4]
